import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/12 15:08
 * @description 动态规划
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.tilingRectangle(5,8);
    }
    public int tilingRectangle(int n, int m) {
        // dp[i][j]为铺设 i，j面积所需要的最少正方形
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][1] = i;
        }
        for (int i = 1; i <= m; i++) {
            dp[1][i] = i;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j<= m; j++) {
                if (i == j) {
                    dp[i][j] = 1;
                }
                if (j > i) {
                    break;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 1; k <= Math.min(i, j); k++) {
                    int temp = Math.min(dp[i-k][j] + dp[k][j], dp[i][j-k] + dp[i][k]);
                    if (dp[i][j] != 0) {
                        dp[i][j] = Math.min(dp[i][j], temp);
                    }else {
                        dp[i][j] =  temp ;
                    }
                }
            }
        }
        return dp[n][m];
    }
}
